package jp.ac.nii.icpc2010.players;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Vector;
import java.util.Comparator;

import jp.ac.nii.icpc2010.ITron;
import jp.ac.nii.icpc2010.playfield.FieldDirection;
import jp.ac.nii.icpc2010.playfield.IPlayField;

/**
 * 
 * @Strategy Breadth-First-Search
 * @author Naoki
 * 
 */

public class YourOwnPlayer extends BasePlayer {
	public YourOwnPlayer(int id, IPlayField playField) {
		super(id, playField);
	}

	FieldDirection prev_dir = null;
	public static int MAGIC_NUMBER = 20;
	public static int SAFTEY_MAGIC_NUMBER = 50;
	public static boolean DEBUG = false;
	public static boolean safety_condition = true;

	public static int maxTime() {
		if (safety_condition)
			return SAFTEY_MAGIC_NUMBER;
		return MAGIC_NUMBER;
	}

	public static int turn = 0;

	public int getRemainingTime(String str) {
		if (DEBUG) {
			System.out.println("[" + turn + "]" + str + " "
					+ super.getRemainingTime() + " "
					+ (Runtime.getRuntime().freeMemory() >> 20) + "/"
					+ (Runtime.getRuntime().maxMemory() >> 20));

		}
		return super.getRemainingTime();
	}

	public FieldDirection getInput() {
		turn++;
		return BFS();
	}

	public FieldDirection BFS() {

		LinkedList<Struct> structList = new LinkedList<Struct>();
		Queue<Struct> structQ = (Queue<Struct>) structList;

		Struct st, newSt, root = new Struct(getX(), getY(), getPlayField());
		structQ.add(root);

		FieldDirection direction;

		if (prev_dir != null) {
			int[] pred = getPlayField().stepOne(getX(), getY(), prev_dir);
			safety_condition = isSafe(pred[0], pred[1]) ? false : true;
		}

		queueBreak: while (structQ.size() > 0) {
			if (getRemainingTime("A") < maxTime())
				break;

			st = structQ.remove();
			Iterator<FieldDirection> it = st.getField().getSafeDirs(st.getX(),
					st.getY()).iterator();
			while (it.hasNext()) {

				if (getRemainingTime("B") < maxTime())
					break queueBreak;

				direction = it.next();

				newSt = new Struct(st.getX(), st.getY(), st.getEnemyX(), st
						.getEnemyY(), direction, st.getField(), st);
				st.addChildStruct(newSt);

				structQ.add(newSt);
			}
		}

		prev_dir = root.getDecision();
		return prev_dir;

	}

	private int evalDirection(Struct st) {
		return st.isCoin ? 200 : 0;
	}

	private int evalStruct(Struct st) {
		int score = 0, deadEnd = 0;
		OriginalField f = st.getField();
		for (FieldDirection dir : getDirs()) {
			int[] pred = f.stepOne(st.getX(), st.getY(), dir);
			if (f.isCoin(pred[0], pred[1])) {
				score += 0;
			} else if (f.isFree(pred[0], pred[1])) {
			} else if (f.isMyTron(pred[0], pred[1])) {
				score -= 0;
				deadEnd++;
			} else if (f.isEnemyTron(pred[0], pred[1])) {
				score -= 0;
				deadEnd++;
			} else if (f.isWall(pred[0], pred[1])) {
				score -= 0;
				deadEnd++;
			}
		}

		if (deadEnd >= 4)
			score -= 10000;
		return score;
	}

	public class OriginalField implements IPlayField {

		private int[][] field;// int[x][y]

		public OriginalField(int x, int y) {
			this.field = new int[x][y];
		}

		public OriginalField(IPlayField f, int x, int y, FieldDirection dir) {
			this.field = new int[f.getWidth()][f.getHeight()];
		}

		public void copyField(IPlayField f) {
			for (int i = 0; i < f.getWidth(); i++) {
				for (int j = 0; j < f.getHeight(); j++) {
					setObjectAt(f.getObjectAt(i, j), i, j);
				}
			}

		}

		public void changeField(int x1, int y1, int x2, int y2, Struct st) {
			setObjectAt(OBJECT_WALL, x1, y1);
			setObjectAt(OBJECT_WALL, x2, y2);
			setObjectAt(OBJECT_FREE, st.getX(), st.getY());
			setObjectAt(OBJECT_FREE, st.getEnemyX(), st.getEnemyY());
		}

		// public void changeField(int x, int y, FieldDirection dir) {
		// changeField(x, y, stepOne(x, y, dir)[0], stepOne(x, y, dir)[1]);
		// }

		public void print() {
			for (int j = 0; j < getHeight(); j++) {
				for (int i = 0; i < getWidth(); i++) {
					System.out.format("%3d", field[i][j]);
				}
				System.out.println("");
			}

		}

		public int getHeight() {
			return field[0].length;
		}

		public int getNumOfPlayers() {
			return 0;
		}

		@Override
		public int getObjectAt(int arg0, int arg1) {
			return field[arg0][arg1];
		}

		public void setObjectAt(int object, int x, int y) {
			field[x][y] = object;
		}

		@Override
		public Vector<ITron> getTrons() {
			return null;
		}

		@Override
		public int getWidth() {
			return field.length;
		}

		public boolean isSafe(int x, int y) {
			return (isFree(x, y) || isCoin(x, y)) && !isTron(x, y);
		}

		public boolean isTron(int x, int y) {
			return (isMyTron(x, y) || isEnemyTron(x, y));
		}

		public boolean isEnemyTron(int x, int y) {
			int chip = 0;
			try {
				chip = getObjectAt(x, y);
			} catch (ArrayIndexOutOfBoundsException e) {
				return false;
			}

			for (int enemyId : getEnemyIds()) {
				if (chip == objectTrailOf(enemyId)) {
					return true;
				}
			}
			return false;
		}

		public boolean isMyTron(int x, int y) {
			int chip = 0;
			try {
				chip = getObjectAt(x, y);
			} catch (ArrayIndexOutOfBoundsException e) {
				return false;
			}

			if (chip == objectTrail()) {
				return true;
			} else {
				return false;
			}
		}

		public boolean isWall(int x, int y) {
			int chip = 0;
			try {
				chip = getObjectAt(x, y);
			} catch (ArrayIndexOutOfBoundsException e) {
				return false;
			}

			if (chip == OBJECT_WALL) {
				return true;
			} else {
				return false;
			}
		}

		public boolean isFree(int x, int y) {
			int chip = 0;
			try {
				chip = getObjectAt(x, y);
			} catch (ArrayIndexOutOfBoundsException e) {
				return false;
			}

			if (chip == OBJECT_FREE) {
				return true;
			} else {
				return false;
			}
		}

		public boolean isCoin(int x, int y) {
			int chip = 0;
			try {
				chip = getObjectAt(x, y);
			} catch (ArrayIndexOutOfBoundsException e) {
				return false;
			}

			if (chip == OBJECT_COIN) {
				return true;
			} else {
				return false;
			}
		}

		@Override
		public int[] stepOne(int arg0, int arg1, FieldDirection arg2) {
			return getPlayField().stepOne(arg0, arg1, arg2);
		}

		public List<FieldDirection> getSafeDirs(int x, int y) {
			ArrayList<FieldDirection> result = new ArrayList<FieldDirection>();

			for (FieldDirection dir : getDirs()) {
				int[] pred = stepOne(x, y, dir);
				if (isSafe(pred[0], pred[1])) {
					result.add(dir);
				}
			}
			return result;
		}
	}

	public class Struct {
		private int newX, newY, enemyX, enemyY;
		private boolean isCoin;
		private FieldDirection direction;
		private OriginalField f;
		private Struct parentStruct;
		private LinkedList<Struct> childStruct = new LinkedList<Struct>();

		public Struct(int firstX, int firstY, IPlayField nowField) {

			this.newX = firstX;
			this.newY = firstY;

			f = new OriginalField(nowField.getWidth(), nowField.getHeight());
			f.copyField(nowField);
		}

		public Struct(int nowX, int nowY, int enemyX, int enemyY,
				FieldDirection direction, OriginalField nowField, Struct parent) {
			newX = nowField.stepOne(nowX, nowY, direction)[0];
			newY = nowField.stepOne(nowX, nowY, direction)[1];
			this.parentStruct = parent;

			isCoin = nowField.isCoin(newX, newY);

			f = new OriginalField(getPlayField().getWidth(), getPlayField()
					.getHeight());
			f.copyField(nowField);
			f.changeField(nowX, nowY, enemyX, enemyY, this);

			this.direction = direction;

		}

		public int getChildDepth() {
			int max = 0;
			if (childStruct.isEmpty())
				return 0;

			for (Struct child : childStruct) {
				int depth = child.getChildDepth();
				if (max < depth)
					max = depth;
			}
			return 1 + max;
		}

		public FieldDirection getDecision() {
			FieldDirection decision = (f.getSafeDirs(newX, newY).isEmpty()) ? prev_dir
					: f.getSafeDirs(newX, newY).get(0);
			if (parentStruct != null)
				return decision;
			int maxScore = Integer.MIN_VALUE;
			int curScore;
			for (Struct child : childStruct) {

				// if (getRemainingTime("Resume Recursive Call @ GetDecision"
				// + "(Decision)" + decision) < 2)
				// return decision;

				curScore = child.getScore();
				if (maxScore <= curScore) {
					maxScore = curScore;
					decision = child.getDirection();
				}
			}
			System.out.println("[" + turn + "] Depth:" + getChildDepth()
					+ " Score:" + maxScore + " Decision:" + decision);

			return decision;

		}

		public int getScore() {
			if (childStruct.isEmpty())
				return evalDirection(this) + evalStruct(this);

			int maxScore = -10000;
			for (Struct st : childStruct) {
				int childScore = evalDirection(this) + st.getScore();
				if (maxScore < childScore)
					maxScore = childScore;

				// if (getRemainingTime("Resume Recursive Call @ GetScore "
				// + maxScore) < maxTime())
				// return maxScore;

			}
			return maxScore;
		}

		public Struct getRootStruct() {
			if (parentStruct == null)
				return this;
			return getParentStruct().getRootStruct();
		}

		public Struct getStruct() {
			return this;
		}

		public OriginalField getField() {
			return f;
		}

		public int getY() {
			return newY;
		}

		public int getX() {
			return newX;
		}

		public int getEnemyY() {
			return enemyY;
		}

		public int getEnemyX() {
			return enemyX;
		}

		public FieldDirection getDirection() {
			return direction;
		}

		public Struct getParentStruct() {
			return parentStruct;
		}

		public LinkedList<Struct> getChildStruct() {
			return childStruct;
		}

		public void addChildStruct(Struct child) {
			childStruct.add(child);
		}
	}

	public class ScoreDscComparator implements Comparator<Struct> {
		public int compare(Struct arg0, Struct arg1) {
			return arg1.getScore() - arg0.getScore();
		}
	}
}